package everyday;

import common.TreeNode;

/**
 * @author zhangmin
 * @create 2022-04-27 17:15
 */
public class maxPathSum124 {
    //求单边最长路径，然后再维护最大路径
    int maxPath=Integer.MIN_VALUE;
    int oneSideSum(TreeNode root){
        if (root==null) return 0;
        int leftSum = Math.max(0, oneSideSum(root.left));
        int rightSum = Math.max(0, oneSideSum(root.right));
        maxPath=Math.max(maxPath,leftSum+rightSum+root.val);
        return Math.max(leftSum,rightSum)+root.val;
    }
    public int maxPathSum(TreeNode root) {
        oneSideSum(root);
        return maxPath;
    }
}
